//
// Created by Administrator on 2022/2/20.
//

#ifndef CPP_LEARNING_KMP_H
#define CPP_LEARNING_KMP_H
#include <strings.h>
int * buildNext(char*P){
    int m = strlen(P) , j = 0;

    int * N = new int[m];
    int t = N[0] = -1;        // Next[-1] 为通配符

    while(j < m-1){
        if(t < 0 || P[j] == P[t]){   // P[j] == P[next[j]]   next[j] = t;
            N[++j] = ++t;
        }else{
            t = N[t];
        }
    }
    return N;
}
int kmp_match(char*P, char* T){
    int * next = buildNext(P);
    int n = strlen(T) , i = 0;
    int m = strlen(P) , j = 0;

    while (j<m && i<n){
        if(T[i] == P[j] || j < 0){
            i++;
            j++;
        }else{
            j = next[j];
        }
    }
    delete [] next;
    return i-j;
}
#endif //CPP_LEARNING_KMP_H
